//
// Created by 啊汤哥 on 2025/6/24.
//

// 链式存储实现的队列
#include <stdio.h>
#include <stdlib.h>

typedef struct LinkNode {
    int data;
    struct LinkNode *next;
};

typedef struct {
    LinkNode *front, *rear; // 队列的对头和队尾
} LinkQueue;

// 初始化  带头结点
void InitHeadQueue(LinkQueue *q) {
    q->front = q->rear = (LinkNode *) malloc(sizeof(LinkNode));
    q->front->next = NULL;
}

// 不带头结点
void InitNoHeadQueue(LinkQueue *q) {
    q->front = NULL;
    q->rear = NULL;
}

// 判断队列是否为空
bool EmptyQueue(LinkQueue q) {
    if (q.front == q.rear) {
        return true;
    }
    return false;
}

// 入队带头结点 --
void EnHeadQueue(LinkQueue *q, int x) {
    LinkNode *s = (LinkNode *) malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    q->rear->next = s; // 新节点插入到rear之后
    q->rear = s; // 修改队尾指针
}

// 入队不带带头结点 --
void EnNoHeadQueue(LinkQueue *q, int x) {
    LinkNode *s = (LinkNode *) malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    if (q->front == NULL) { // 不带头结点的队列，第一个元素要特点处理
        q->front = s;
        q->rear = s;
    } else {
        q->rear->next = s; // 新节点插入到rear之后
        q->rear = s; // 修改队尾指针
    }
}

// 带头节点的出队
bool DeHeadQueue(LinkQueue &q, int &x) {
    if (EmptyQueue(q)) {
        return false;
    }
    LinkNode *p = q.front->next; // 指向头结点
    x = p->data;
    q.front->next = p->next; // 修改头结点的指针
    if (q.rear == p) {  // 如果是最后一个节点出队 q.rear指向的事最后一个节点
        q.rear = q.front;
    }
    free(p);
    return true;
}

// 不带头节点的出队
bool DeNoHeadQueue(LinkQueue &q, int &x) {
    if (q.front == NULL) {
        return false;
    }

    LinkNode *p =q.front;
    x = p->data;
    q.front = p->next;
    if (q.rear == NULL) {
        q.front = NULL;
        q.rear = NULL;
    }
    free(p);
    return true;
}